home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 6942 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.2 KB  |  53 lines
  1. Newsgroups: comp.sys.amiga.programmer
  2. Path: news.ifm.liu.se!liuida!news
  3. From: c92manen@und.ida.liu.se (Mans Engman)
  4. Subject: Re: 680X0 -> PPC translator?
  5. X-Nntp-Posting-Host: astmatix.ida.liu.se
  6. Message-ID: <1586.6669T961T2657@und.ida.liu.se>
  7. Sender: news@ida.liu.se
  8. Organization: CIS Dept, Linkoping University, Sweden
  9. X-Newsreader: THOR 2.22 (Amiga;TCP/IP) *UNREGISTERED*
  10. References: <31499F8E.26A9@netvision.net.il> <volker.0fw1@vb.franken.de>
  11.     <315800D7.1854@sapiens.com> <volker.0g32@vb.franken.de>
  12.     <315C198B.49C2@netvision.net.il> <volker.0g5w@vb.franken.de>
  13.     <1996Apr2.230841.8275@scala.scala.com> <31640B0C.23F5@netvision.net.il>
  14. Date: Fri, 5 Apr 1996 15:01:53 GMT
  15.  
  16. Once you think a bit, it's easy to show (prove!) that static code<->data
  17. distinction can't be determined by an algorithm. It is what theorists call
  18. an "undecidable" problem. Granted, for a "real" computer with a finite amount
  19. of memory/indata it can be "solved" by brute-force search, but this is
  20. not a practical approach.
  21.  
  22. Okay, let's go on:
  23.  
  24. 1) Hilberts 10th problem is a well known, proven undecidable problem. The
  25. problem is determining whether an integer polynomial equation has a
  26. (integer) solution.
  27.  
  28. Example: Does 3x^2 + 2xy + 9x + 5 = 0 have a solution for some integers x, y?
  29. In this case we can of course easily see that it doesn't, but an algorithm
  30. *can't* decide this for arbitrary equations, except for the special case of
  31. 1st degree polynomials (Euclides! :).
  32.  
  33. 2) Now imagine a program calculating some function on the indata x, y, ...
  34. and uses the result as a pc-relative address where we jump. This function,
  35. and the rest of the program can be constructed such that for all x, y, ...
  36. we jump to a legal piece of code. Between these code chunks we will of
  37. course put data to confuse anyone analysing the program! :)
  38.  
  39. 3) An algorithm that can determine code reachability of this program,
  40. would either:
  41.  
  42. i)  try different combinations of inputs and simulate the program. Inputs
  43. include outside calls, memory reads (that may change anytime), or other
  44. undecidable functions. To be sure the algorithm would have to try *all* of
  45. them. Combinatorial-explosion-city?
  46.  
  47. ii) include an algorithm to solve the "10th", which is proven impossible.
  48.  
  49. QED.
  50.  
  51. /Mans (.sig being recompiled)
  52.  
  53.